#include<iostream>
#include<vector>
using namespace std;
/*
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
只使用数字1到9
每个数字 最多使用一次 
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
解题思路：
先定义两个全局变量来存放结果，一维数组path，二维数组result
然后遍历1-n，若先将1放入path则需要向下递归（向下递归树形结构，startIndex++）深度遍历完后考虑横向遍历树形结构
由于我们先放入1后接着要考虑2-9，再放入2后此时path中有1，2两个元素，若我们先放入2，此时我们就只需要考虑3-9了
因为若还是要考虑1-9的话这样就会造成path中的元素重复,所以使用for循环并且在递归后恢复栈中状态来实现横向遍历
代码逻辑为：
for(int i=startIndex;i<=n;i++)
{
    sum+=i;
    path.push_back(i);
    trackbacking(k,n,sum,startIndex++);//此为深度遍历，逻辑为每个根节点往下进行深度遍历
    //这里的重点是要恢复栈状态，就是恢复path和sum的值从而达到遍历根节点的其他节点的目的
    sum-=i;
    path.pop_back();
}
如何进行剪枝呢，倘若在sum没有达到递归终止条件的要求但已经超出n的值时就需要提前终止递归
*/


//创建全局变量
vector<vector<int>> result;
vector<int> path;
void trackbacking(int k,int n,int sum,int startIndex)
{
    //递归终止条件
    if(path.size()==k)
    {
        //若path长度为k且sum的值等于n
        if(sum==n)
            result.push_back(path);
        return;
    }
    for(int i=startIndex;i<10;i++)
    {
        sum+=i;
        path.push_back(i);
        //剪枝操作,此时已经添加元素导致sum>n,所以要剪枝的话必须要先做回溯操作
        if(sum>n)
        {
            sum-=i;
            path.pop_back();
            return;
        }  
        trackbacking(k,n,sum,++startIndex);
        //恢复现场
        sum-=i;
        path.pop_back();
    }
    
}
vector<vector<int>> combinationSum3(int k, int n) {
    trackbacking(k,n,0,1);
    return result;
}
int main()
{
    cout<<"enter a k:"<<endl;
    int k;
    cin>>k;
    cout<<"enter a n:"<<endl;
    int n;
    cin>>n;
    vector<vector<int>>result = combinationSum3(k,n);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[0].size();j++)
        {
            cout<<result[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}